Image compression techniques reduce the memory required for storage of large or complex images, permitting storage of images in devices with limited memory. For example, image compression techniques used in digital copiers and scanners assist in storage of complex images for subsequent printing. Similarly, image compression benefits communication links where bandwidth limitations would otherwise render transmission of image data impractical. Image compression also offers substantial benefits for archiving large image libraries.
JPEG (Joint Photographic Experts Group) is a standardized image compression technique that can be used with either full-color or gray-scale images. This technique performs a Discrete Cosine Transform (DCT) on each block of pixels in an image. The result of the DCT for each block of pixels is an array of frequency components. Low frequency components correspond to slowly varying intensities between neighboring pixels. High frequency components represent rapidly varying intensities across small clusters of pixels. Information represented by the higher frequency components is reduced by quantization, i.e., the restriction of actual values to a limited set of values. The compressed image size is related to the quantization level specified by the user. The frequency components are encoded in order from the lowest frequency to the highest. If there are no frequency components beyond a specific frequency, then no further data from that block is encoded. Instead, an end of block symbol is emitted to indicate to a decoder that the block is complete.
Application of the above technique to blocks of pixels having high spatial frequencies may result in data represented by more bits than can be stored in a memory device or transmitted over a communication link in a limited time. One technique used to overcome this problem is to count the total number of bits used to represent the block of pixels and compare the total with a maximum allowable value. If the total exceeds the maximum value, the highest non-zero frequency component is decreased in absolute value and the total number of bits is recalculated and compared with the maximum. This process is repeated until the total number of bits is no greater than the maximum value. Generally, human perception of images is more affected by amplitude changes in the lower frequency components than higher frequency components, therefore this technique typically has negligible impact on perceived image quality. However, an image stored under the JPEG standard and subsequently recalled is reduced in quality from the original image. Multiple applications of JPEG compression on an image can result in a significant reduction in the image quality. It is therefore desirable to store as many of the higher frequency components as possible in the available memory.
One known storage technique for JPEG compressed images, described in U.S. Pat. No. 5,321,522, provides fixed memory allocation for each block of pixels. Therefore, a block of pixels that has no high frequency components may not require all the bits available in a block of memory. As a result, there can be "gaps" in memory. Subsequent processing, however, may include blocks of pixels with high frequency information that exceeds the available memory allocated to individual blocks, thereby requiring the loss of some information.